Sudoku Solver

Description

Posted by Marcel Samek in MoHPC - HP Articles Forum

This program uses a backtracking algorithm to find the first solution to a Sudoku puzzle.

You have to save the starting puzzle in registers R₈ - R₁₆. Each row of the sudoku is represented as a single, 9 digit number, with 0 representing each blank.
Once you have done that, you can run the program with a GSB A. When it is complete, you will find the solution to the sudoku puzzle in registers R₁₇ to R₂₅.
You will need to use the indirect register (i) to get at the result, because there is no way to directly see the value of register R₂₀ and above.

Before entering the program perform the following: 3 4 DIM (i)

Example 1:

•12|•••|57• 12000570 STO 8
6••|5•1|••4 600501004 STO 9
4••|•2•|••8 400020008 STO . 0
———————————
•2•|•1•|•5• 20010050 STO . 1
••4|9•7|8•• 4907800 STO . 2
•7•|•8•|•1• 70080010 STO . 3
———————————
7••|•9•|••5 700090005 STO . 4
5••|4•8|••6 500408006 STO . 5
•38|•••|94• 38000940 STO . 6

Solution:



  912|846|573

  683|571|294

  457|329|168

  ———————————

  829|613|457

  164|957|832

  375|284|619

  ———————————

  746|192|385

  591|438|726

  238|765|941

To recall the results from Register R₁₇ to R₂₅ enter 17 STO I RCL (i) and so on.

Program Resources

Labels

Name	Description	Name	Description
A	Sudoku Solver	3	# Set the indirect register and remove the parameters from the stack
B	# Utility subroutine for setting flag matrix values	4	# Extract value at the current column from the matrix indirectly specified by x&y
C	# Backs up to the previous position	5	# Sets the utility temp register to 2^(x-1). Leaves x in place.
D	# Set/clear flag matrix values	6	# Increments or decrements the current position in the trial solution.
E	# Main solution loop	7	# Set the value x into the current row/column in the trial solution.
1	# Returns the integer representing of the entire Xth row of the flag matrix	8	# Check the possible digits in order 1-9
2	# Set the flags to show the input values are set	9	# Get the appropriate row (x) from the flag matrix

Storage Registers

Name	Description	Name	Description
0	General purpose variable used for miscelaneous purposes	5	Power of 10 of current column index
1	Current index (0-80) in the pseudo-recursion	6	Value in the test solution at current index
2	Row (0-8) of current index	7	Value of start clue at current index (0 if not set)
3	Column (0-8) of current index	(i)
4	Block # (0-8) of current index	I

Flags

Number	Description
2	Indicates that a digit has been used in cur row/column/block
3	Input to Subroutine B (whether to set or clear flags)

Program

Line	Display	Key Sequence	Line	Display	Key Sequence	Line	Display	Key Sequence
000			065	7	7	130	43, 5, 2	g CF 2
001	42,21,14	f LBL D	066	32 4	GSB 4	131	45 2	RCL 2
002	32 5	GSB 5	067	44 6	STO 6	132	32 9	GSB 9
003	45 2	RCL 2	068	45 2	RCL 2	133	43, 6, 2	g F? 2
004	32 12	GSB B	069	8	8	134	22 8	GTO 8
005	45 3	RCL 3	070	32 4	GSB 4	135	45 3	RCL 3
006	32 12	GSB B	071	44 7	STO 7	136	32 9	GSB 9
007	45 4	RCL 4	072	43 32	g RTN	137	43, 6, 2	g F? 2
008	42,21,12	f LBL B	073	42,21, 4	f LBL 4	138	22 8	GTO 8
009	32 1	GSB 1	074	32 3	GSB 3	139	45 4	RCL 4
010	45 0	RCL 0	075	45 24	RCL (i)	140	32 9	GSB 9
011	43, 6, 3	g F? 3	076	45,10, 5	RCL ÷ 5	141	43, 6, 2	g F? 2
012	16	CHS	077	43 44	g INT	142	22 8	GTO 8
013	40	+	078	1	1	143	45 6	RCL 6
014	34	x↔y	079	0	0	144	32 14	GSB D
015	2	2	080	10	÷	145	22 15	GTO E
016	6	6	081	42 44	f FRAC	146	42,21,13	f LBL C
017	32 3	GSB 3	082	1	1	147	1	1
018	44 24	STO (i)	083	0	0	148	16	CHS
019	33	R⬇	084	20	×	149	32 6	GSB 6
020	9	9	085	43 32	g RTN	150	43,30, 1	g TEST x>0
021	40	+	086	42,21,11	f LBL A	151	22 13	GTO C
022	22 5	GTO 5	087	43, 5, 2	g CF 2	152	45 6	RCL 6
023	42,21, 7	f LBL 7	088	43, 5, 3	g CF 3	153	43, 4, 3	g SF 3
024	42, 4, 6	f Χ↔ 6	089	1	1	154	32 14	GSB D
025	44 0	STO 0	090	16	CHS	155	43, 5, 3	g CF 3
026	45 2	RCL 2	091	44 1	STO 1	156	22 8	GTO 8
027	1	1	092	42,21, 2	f LBL 2	157	42,21, 9	f LBL 9
028	7	7	093	1	1	158	32 1	GSB 1
029	32 3	GSB 3	094	32 6	GSB 6	159	45,10, 0	RCL ÷ 0
030	45 24	RCL (i)	095	45 7	RCL 7	160	43 44	g INT
031	45 6	RCL 6	096	32 7	GSB 7	161	2	2
032	45,30, 0	RCL − 0	097	45 7	RCL 7	162	10	÷
033	45,20, 5	RCL × 5	098	43,30, 1	g TEST x>0	163	42 44	f FRAC
034	40	+	099	32 14	GSB D	164	43,30, 1	g TEST x>0
035	44 24	STO (i)	100	8	8	165	43, 4, 2	g SF 2
036	43 32	g RTN	101	0	0	166	33	R⬇
037	42,21, 6	f LBL 6	102	45 1	RCL 1	167	33	R⬇
038	44,40, 1	STO + 1	103	43,30, 6	g TEST x≠y	168	9	9
039	45 1	RCL 1	104	22 2	GTO 2	169	40	+
040	45 1	RCL 1	105	1	1	170	22 5	GTO 5
041	9	9	106	16	CHS	171	42,21, 5	f LBL 5
042	10	÷	107	44 1	STO 1	172	44 0	STO 0
043	43 44	g INT	108	42,21,15	f LBL E	173	1	1
044	44 2	STO 2	109	8	8	174	30	−
045	9	9	110	0	0	175	2	2
046	20	×	111	45 1	RCL 1	176	34	x↔y
047	30	−	112	43,30, 5	g TEST x=y	177	14	yˣ
048	44 3	STO 3	113	43 32	g RTN	178	42, 4, 0	f Χ↔ 0
049	3	3	114	1	1	179	43 32	g RTN
050	10	÷	115	32 6	GSB 6	180	42,21, 1	f LBL 1
051	45 2	RCL 2	116	45 7	RCL 7	181	36	ENTER
052	3	3	117	43,30, 1	g TEST x>0	182	36	ENTER
053	10	÷	118	22 15	GTO E	183	2	2
054	43 44	g INT	119	32 7	GSB 7	184	6	6
055	3	3	120	42,21, 8	f LBL 8	185	32 3	GSB 3
056	20	×	121	9	9	186	45 24	RCL (i)
057	40	+	122	45 6	RCL 6	187	43 32	g RTN
058	44 4	STO 4	123	43,30, 5	g TEST x=y	188	42,21, 3	f LBL 3
059	8	8	124	22 13	GTO C	189	40	+
060	45,30, 3	RCL − 3	125	1	1	190	44 25	STO I
061	13	10ˣ	126	40	+	191	33	R⬇
062	44 5	STO 5	127	32 7	GSB 7	192	43 32	g RTN
063	45 2	RCL 2	128	45 6	RCL 6
064	1	1	129	32 5	GSB 5